package trees;

import beans.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 *
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回锯齿形层次遍历如下：
 *
 * [
 *   [3],
 *   [20,9],
 *   [15,7]
 * ]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

public class ZigzagLevelOrder {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean rightFlag = true;
        int curLevel = 1;
        int nextLevel = 0;
        List<Integer> list = new ArrayList<>();
        while(!queue.isEmpty()){
            root = queue.poll();
            list.add(root.val);
            int childIndex = curLevel + 1;
            if(rightFlag){
                if(addNodeToQueue(queue, root.right, childIndex)){
                    nextLevel ++;
                }
                if(addNodeToQueue(queue, root.left, childIndex)){
                    nextLevel ++;
                }
            } else {
                if(addNodeToQueue(queue, root.left, childIndex)){
                    nextLevel ++;
                }
                if(addNodeToQueue(queue, root.right, childIndex)){
                    nextLevel ++;
                }
            }
            curLevel --;
            if(curLevel == 0){
                curLevel = nextLevel;
                nextLevel = 0;
                result.add(list);
                list = new ArrayList<>();
                rightFlag = !rightFlag;
            }
        }

        return result;
    }

    private boolean addNodeToQueue(LinkedList<TreeNode> queue, TreeNode node, int index){
        if(node != null){
            queue.add(index, node);
            return true;
        }
        return false;
    }

}
